package com.sali.Tree;

import java.util.Stack;

/**
 二叉搜索树的后序遍历序列
 */
public class JZ_33 {

    /*
    * 例子：
    * 有效 BST 后序序列（返回 true）
    * 后序遍历顺序：左子树（1→4→3）→右子树（7→9→8）→根（5），因此序列为 [1,4,3,7,9,8,5]
    *       5
          /   \
         3     8
        / \   / \
        1  4  7  9
       （根->右->左）代码执行步骤：
       * Step1: 5 -> 栈：{5}, root: MAX
       * Step2: 8 -> 栈{5, 8}: root: MAX
       * Step3: 9 -> 栈{5, 8, 9} root: MAX
       * Step4: 7 -> 栈{5, 7} root: 8
       * Step5: 3 -> 栈{3} root: 5
       * Step6: 4 -> 栈{3,4} root: 5
       * Step7: 1 -> 栈{1} root: 4
    * */

    /*
     * 例子：
     * 无效 BST 后序序列（返回 false）
    *       5
          /   \
         3     8
        / \   / \
        1  4  9  7
        * Step1: 5 -> 栈：{5}, root: MAX
        * Step2: 8 -> 栈{5, 8}: root: MAX
        * Step3: 7 -> 栈{5, 7} root: 8
        * Step4: 9 -> 9 > root, False
     * */

    /*
    * 后序遍历的逆序是「根→右→左」。
    * 代码通过栈保存右子树节点
    * 当遇到左子树节点时（当前节点小于栈顶元素），弹出栈顶元素作为其父节点（root），并确保后续左子树节点都小于该父节点。
    * */
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 处理序列为空情况
        if(sequence.length == 0) return false;

        Stack<Integer> s = new Stack<>();
        int root = Integer.MAX_VALUE;
        // 以根，右子树，左子树顺序遍历
        for(int i = sequence.length - 1; i >= 0; i--) {
            // 确定根后一定是在右子树节点都遍历完了，因此当前sequence未遍历的节点中只含左子树，左子树的节点如果>root则说明违背二叉搜索的性质
            if(sequence[i] > root) return false;
            // 进入左子树的契机就是sequence[i]的值小于前一项的时候，这时可以确定root
            while(!s.isEmpty() && s.peek() > sequence[i]) {
                root = s.pop();
            }
            // 每个数字都要进一次栈
            s.add(sequence[i]);
        }
        return true;
    }

}
